//
// Created by francklinson on 2021/6/27.
//
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

class Solution {
public:
    int snakesAndLadders(vector<vector<int>> &board) {
        /**
         * BFS
         */
        auto N = board.size();
        unsigned int target = N * N;
        // 队列，存放位置和执行的步数
        queue<pair<int, int>> q;
        q.emplace(1, 0);
        vector<bool> seen(target, false);
        while (!q.empty()) {
            auto curIndex = q.front().first;
            auto level = q.front().second;
            q.pop();
            // 下一步6种方案
            for (int i = 1; i <= 6; ++i) {
                auto nextIndex = curIndex + i;
                if (nextIndex > target) break;
                // 判断下一个位置有没有蛇或者梯子
                auto rc = index2Matrix(nextIndex, N);
                // 遇到梯子或者蛇
                if (board[rc.first][rc.second] > 0) {
                    nextIndex = board[rc.first][rc.second];
                }
                if (nextIndex == target) return level + 1;
                if (!seen[nextIndex]) {
                    seen[nextIndex] = true;
                    q.emplace(nextIndex, level + 1);
                }

            }
        }


        return -1;
    }

    /**
     * 把序号变成矩阵坐标
     * 分行 列 讨论
     * row = N-1-index/N
     * col =
     * @param index
     * @return
     */
    pair<int, int> index2Matrix(int index, unsigned int n) {
        unsigned int row = (index - 1) / n, col = (index - 1) % n;
        if (row % 2 == 1) {
            col = n - 1 - col;
        }
        return {n - 1 - row, col};

    }
};

int main() {
    vector<vector<int>> board{
            {-1, -1, -1, -1, -1, -1},
            {-1, -1, -1, -1, -1, -1},
            {-1, -1, -1, -1, -1, -1},
            {-1, 35, -1, -1, 13, -1},
            {-1, -1, -1, -1, -1, -1},
            {-1, 15, -1, -1, -1, -1}
    };
    vector<vector<int>> b2{{-1, -1, -1},
                           {-1, 9,  8},
                           {-1, 8,  9}};
    Solution solution;
    cout << solution.snakesAndLadders(board);
//    auto ans = solution.index2Matrix(18, 6);
//    cout << ans.first << ans.second << endl;
    return 0;
}